package my.leetcode.solution;

import java.util.*;
import java.util.stream.Collectors;

/**
 * 思路:
 */
public class P15 {

    public static void main(String[] args) {
        System.out.println(threeSum(new int[]{-1,0,1,2,-1,-4}));
        System.out.println(threeSum(new int[]{3,0,-2,-1,1,2}));
    }

    public static void put(TreeMap<Integer, Integer> m, Integer k) {
        Integer _v = m.get(k);
        if(_v == null) {
            m.put(k, 1);
        } else {
            m.put(k, _v + 1);
        }
    }

    public static void put(TreeMap<Integer, Integer> m1, TreeMap<Integer, Integer> m2, List<List<Integer>> list) {
        List<Integer> l1 = m1.keySet().stream().collect(Collectors.toList());
        int size = l1.size();
        for(int i = 0;i < size;i++) {
            int a = l1.get(i);
            if(m1.get(a) > 1) {
                add(m2, list, a, a);
            }
            for(int j = i + 1;j < size;j++) {
                add(m2, list, a, l1.get(j));
            }
        }
    }

    public static void add(TreeMap<Integer, Integer> m, List<List<Integer>> list, Integer a, Integer b) {
        int c = a + b;
        if(m.containsKey(-c)) {
            list.add(Arrays.asList(a, b, -c));
        }
    }

    public static List<List<Integer>> threeSum(int[] nums) {
        if(nums == null || nums.length < 3) {
            return Collections.emptyList();
        }
        List<List<Integer>> list = new ArrayList<>();
        TreeMap<Integer, Integer> nm = new TreeMap();
        TreeMap<Integer, Integer> pm = new TreeMap();
        int zeroCount = 0;
        for(int n : nums) {
            if(n == 0) {
                zeroCount++;
            } else if(n > 0) {
                put(pm, n);
            } else {
                put(nm, n);
            }
        }
        if(zeroCount > 2) {
            list.add(Arrays.asList(0,0,0));
        }
        if(zeroCount > 0) {
            for(Integer v : pm.keySet()) {
                if(nm.containsKey(-v)) {
                    list.add(Arrays.asList(v, -v, 0));
                }
            }
        }
        put(nm, pm, list);
        put(pm, nm, list);
        return list;
    }

}
